#include <iostream>
using namespace std;
typedef struct node
{
    int data;
    struct node *next;
}Node,*LNode;

void insertnode(LNode &H,int x)//元素单调不减插入链表
{
    Node *p, *q, *r;//r前驱，p工作指针,q创结点
    r = H;
    p = H->next;
    while(p!=NULL&&p->data<x)
    {
        r = p;
        p = p->next;
    }
    q = new Node;//q待插入
    q->data=x;
    q->next=p;
    r->next=q;//r->q->p
}

void cinnode(LNode &H)//输入元素
{
    H = new Node;
    if(H==NULL)
    {
        cout << "无内存空间可分配" << endl;
        return;
    }
    H->next = NULL;
    int x;
    cin >> x;
    while(x!=0)
    {
        insertnode(H, x);//将元素插入链表
        cin >> x;
    }
}

void outputnode(LNode &H)//输出链表
{
    Node *p;
    p=H->next;
    while(p!=NULL)
    {
        cout << p->data << ' ';
        //printf("%d  ",p->data);
        p=p->next;
    }
}


int main()
{
    LNode H;
    cinnode(H);
    outputnode(H);
    return 0;
}
